class Solution:
    def searchMatrix(self, matrix, target):
        """
        :param matrix: List[List[int]]
        :param target:
        :return:
        """
        # 时间复杂度O(mn)
        for line in matrix:
            if target in line:
                return True
        return False

    def searchMatrix_2(self, matrix, target):
        h = len(matrix)
        if not h:
            return False
        w = len(matrix[0])
        if not w:
            return False
        left = 0
        right = h * w - 1
        # 二分查找 O(logn)
        while left <= right:
            mid = (left + right) // 2
            i = mid // w
            j = mid % w
            if matrix[i][j] == target:
                return True
            if matrix[i][j] > target:
                right = mid - 1
            else:
                left = mid + 1
        else:
            return False


mar = [
    [1, 3, 5, 7],
    [10, 11, 16, 20],
    [23, 30, 34, 50]
]
tar = 3

s = Solution()
print(s.searchMatrix_2(mar, tar))


